package 力扣日常刷题.木22二月.第17天223;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * @author 帅小伙
 * @date 2022/2/23
 * @description
 */
public class Demo137字符串排序 {

    List<String> res = new ArrayList<>();
    boolean[] isUsed;
    public String[] permutation(String s) {
        isUsed = new boolean[s.length()];
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        dfs(chars,new StringBuilder());

        String[] ans = new String[res.size()];
        for (int i = 0; i < res.size(); i++) {
            ans[i] = res.get(i);
        }
        return ans;
    }


    void dfs(char[] chars,StringBuilder sb) {
        if(sb.length() == chars.length){
            res.add(sb.toString());
            return;
        }
        for (int i = 0; i < chars.length; i++) {
            if(isUsed[i]) continue;
            if(i > 0 && chars[i] == chars[i - 1] && isUsed[i - 1]){
                continue;
            }
            sb.append(chars[i]);
            isUsed[i] = true;
            dfs(chars,sb);
            sb.deleteCharAt(sb.length() - 1);
            isUsed[i] = false;
        }
    }
}
